package recursive.numTrees;

import java.util.Arrays;

/**
 * @Date 2020/04/05
 * @author 王光浩
 * @Thinking 使用备忘录模式+递归
 */
public class MymethodTwo {
	private int[] help;
	public int numTrees(int n) {
		help=new int[n-1];
		return recursively(1,n);
	}
	private int recursively(int l,int r) {
		if(l-r<=1)return l-r+1;
		if(help[l-r]!=0)return help[l-r];
		int left,right;
		int count=0;
		for(int i=l;i<=r;i++) {
			left=1;
			right=1;
			if(i!=l)left=recursively(l,i-1);
			if(i!=r)right=recursively(i+1,r);
			count+=left*right;
		}
		help[r-l]=count;
		return help[r-l];
		
	}
}
